%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A sparse weighted digraph $G = (V, E)$, where the vertex set is
  $V = \{1, 2, \dots, n\}$.
\Ensure If $G$ has negative-weight cycles, then return
  \MyFalse. Otherwise, return an $n \times n$ matrix $D$ of shortest-path
  weights and a list $P$ such that $P[v]$ is a parent list resulting
  from running Dijkstra's algorithm on $G$ with start vertex $v$.
%%
%% algorithm body
\State $s \gets$ vertex not in $V$
\State $V' \gets V \cup \{s\}$
\State $E' \gets E \cup \{sv | v \in V\}$
\State $G' \gets$ digraph $(V', E')$ with weight $w(sv) = 0$ for all $v \in V$
\If{$\BellmanFord(G', w, s) = \MyFalse$}
  \State \Return \MyFalse
\EndIf
\State $d \gets$ distance list returned by $\BellmanFord(G', w, s)$
\For{\rm each edge $uv \in E'$}
  \State $\hat{w}(uv) \gets w(uv) + d[u] - d[v]$
\EndFor
\For{\rm each $u \in V$}
  \State $(\hat{\delta}, \hat{P}) \gets$ distance and parent lists returned by $\Dijkstra(G, \hat{w}, u)$
  \State $P[u] \gets \hat{P}$
  \For{\rm each $v \in V$}
    \State $D[u,v] \gets \hat{\delta}[v] + d[v] - d[u]$
  \EndFor
\EndFor
\State \Return $(D, P)$
\end{algorithmic}
